The stable matching problem (also known as the stable marriage problem) is\r\na well-known problem of matching men to women, so that no man and woman, who are\r\nnot married to each other, both prefer each other. Such a problem has a wide variety of\r\npractical applications, ranging from matching resident doctors to hospitals, to matching\r\nstudents to schools or, more generally, to any two-sided market. In the classical stable\r\nmarriage problem, both men and women express a strict preference order over the members\r\nof the other sex, in a qualitative way. Here, we consider stable marriage problems with\r\nweighted preferences: each man (resp., woman) provides a score for each woman (resp.,\r\nman). Such problems are more expressive than the classical stable marriage problems.\r\nMoreover, in some real-life situations, it is more natural to express scores (to model, for\r\nexample, profits or costs) rather than a qualitative preference ordering. In this context, we\r\ndefine new notions of stability and optimality, and we provide algorithms to find marriages\r\nthat are stable and/or optimal according to these notions. While expressivity greatly increases\r\nby adopting weighted preferences, we show that, in most cases, the desired solutions can be\r\nfound by adapting existing algorithms for the classical stable marriage problem. We also\r\nconsider the manipulability properties of the procedures that return such stable marriages.\r\nWhile we know that all procedures are manipulable by modifying the preference lists or\r\nby truncating them, here, we consider if manipulation can occur also by just modifying the\r\nweights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, in some cases, we may increase the possibility of manipulating, and this cannot be\r\navoided by any reasonable restriction on the weights.
Loading....